#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 定义栈节点结构
typedef struct StackNode {
    TreeNode* treeNode;
    struct StackNode* next;
} StackNode;

// 创建栈节点
StackNode* createStackNode(TreeNode* node) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->treeNode = node;
    newNode->next = NULL;
    return newNode;
}

// 入栈操作
void push(StackNode** top, TreeNode* node) {
    StackNode* newNode = createStackNode(node);
    newNode->next = *top;
    *top = newNode;
}

// 出栈操作
TreeNode* pop(StackNode** top) {
    if (*top == NULL) {
        return NULL;
    }
    StackNode* temp = *top;
    TreeNode* node = temp->treeNode;
    *top = (*top)->next;
    free(temp);
    return node;
}

// 判断栈是否为空
int isEmpty(StackNode* top) {
    return top == NULL;
}

// 中序遍历非递归算法
void inorderTraversal(TreeNode* root) {
    StackNode* stack = NULL;  // 初始化栈为空
    TreeNode* current = root;

    while (current != NULL || !isEmpty(stack)) {
        // 将当前节点压入栈，并遍历左子树
        while (current != NULL) {
            push(&stack, current);
            current = current->left;
        }

        // 当前节点为 NULL 时，弹出栈顶节点
        current = pop(&stack);
        if (current != NULL) {
            printf("%d ", current->value);  // 访问节点
            // 遍历右子树
            current = current->right;
        }
    }
}

// 创建一个新的树节点
TreeNode* createNode(int value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(EXIT_FAILURE);
    }
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 主函数
int main() {
    // 创建树的根节点
    TreeNode* root = createNode(1);

    // 创建左子节点
    root->left = createNode(2);

    // 创建右子节点
    root->right = createNode(3);

    // 创建左子节点的左子节点
    root->left->left = createNode(4);

    // 创建左子节点的右子节点
    root->left->right = createNode(5);

    // 打印树的中序遍历结果
    printf("树的中序遍历结果: ");
    inorderTraversal(root);
    printf("\n");

    // 释放内存（省略具体实现）

    return 0;
}
